#ifndef BinaryTree_H
#define BinaryTree_H
#include <cstddef>
#include <new>

#include <stdexcept>
using std::logic_error;
#include <string>
using std::string;
using std::bad_alloc;
class TreeException : public logic_error
{
public:
	TreeException(const string &message = "")
		:logic_error(message.c_str()) {}
};

template<typename T>
class BinaryTree
{
public:
	BinaryTree();
	BinaryTree(const T &rootItem) throw(TreeException);
	BinaryTree(const T &rootItem, BinaryTree &leftTree, BinaryTree &rightTree)
		throw ( TreeException );
	BinaryTree( const BinaryTree &tree) throw (TreeException);
	virtual ~BinaryTree();

	virtual bool isEmpty() const;
	virtual T getRootData() const throw (TreeException);
	virtual void setRootData(const T &newItem) throw (TreeException);

	virtual void attachLeft(const T &newItem) throw ( TreeException );
	virtual void attachRight(const T &newItem) throw ( TreeException );

	virtual void attachLeftSubtree( BinaryTree &leftTree) throw ( TreeException );
	virtual void attachRightSubtree( BinaryTree &rightTree) throw ( TreeException );
	virtual void detachLeftSubtree( BinaryTree &leftTree) throw ( TreeException );
	virtual void detachRightSubtree( BinaryTree &rightTree) throw ( TreeException );
	virtual BinaryTree getLeftSubtree() const throw( TreeException );
	virtual BinaryTree getRightSubtree() const throw( TreeException );

	virtual void preorderTraverse(void (*visit)(T &anItem)) const;
	virtual void inorderTraverse(void (*visit)(T &anItem)) const;
	virtual void postorderTraverse(void (*visit)(T &anItem)) const;

	virtual BinaryTree& operator=(const BinaryTree &rhs) throw ( TreeException );
protected:
	struct TreeNode
	{
		TreeNode() {};
		TreeNode(const T &nodeItem, TreeNode *Left = NULL, TreeNode * Right = NULL)
			:item(nodeItem), leftChildPtr(Left), rightChildPtr(Right) {}
		T item;
		TreeNode * leftChildPtr;
		TreeNode * rightChildPtr;
	};
	BinaryTree(TreeNode *nodePtr); //protected constructor
	
	void copyTree(TreeNode * treePtr, TreeNode ** newTreePtr) const
		throw( TreeException );

	void destroyTree( TreeNode ** treePtr );
	TreeNode ** rootPtr() {return &root;}
	TreeNode * rootPtr() const {return root;} 
	void setRootPtr(TreeNode *newRoot);

	void getChildPtrs(TreeNode *nodePtr, TreeNode **leftChildPtr, 
		TreeNode **rightChildPtr) const;
	void setChildPtrs(TreeNode *nodePtr, TreeNode *leftChildPtr, 
		TreeNode *rightChildPtr);

	void preorder( TreeNode *treePtr, void (*visit)(T &anItem)) const;
	void inorder( TreeNode *treePtr, void (*visit)(T &anItem)) const;
	void postorder( TreeNode *treePtr, void (*visit)(T &anItem)) const;
private:
	TreeNode *root;
};

//***********************************************************************
//*						BinaryTree Implementation
//***********************************************************************
template<typename TreeItemType>
BinaryTree<TreeItemType>::BinaryTree() : root(NULL)
{
}  // end default constructor

template<typename TreeItemType>
BinaryTree<TreeItemType>::BinaryTree(const TreeItemType& rootItem)
   throw(TreeException)
{
   try
   {
      root = new TreeNode(rootItem, NULL, NULL);
   }
   catch (std::bad_alloc e)
   {  delete root;
      throw TreeException("TreeException: constructor cannot allocate memory");
   }  // end try
}  // end constructor

template<typename TreeItemType>
BinaryTree<TreeItemType>::BinaryTree(const TreeItemType& rootItem,
                       BinaryTree& leftTree,
                       BinaryTree& rightTree)
   throw(TreeException)
{
   try
   {
      root = new TreeNode(rootItem, NULL, NULL);

      attachLeftSubtree(leftTree);
      attachRightSubtree(rightTree);
   }
   catch (bad_alloc e)
   {  delete root;
      throw TreeException(
	 "TreeException: constructor cannot allocate memory");
   }  // end try
}  // end constructor

template<typename TreeItemType>
BinaryTree<TreeItemType>::BinaryTree(const BinaryTree& tree)
   throw(TreeException)
{
   try
   {
      copyTree(tree.root, &root);
   }
   catch (bad_alloc e)
   {  
      destroyTree(rootPtr());
      throw TreeException(
	 "TreeException: copy constructor cannot allocate memory");
   }  // end try
}  // end copy constructor

template<typename TreeItemType>
BinaryTree<TreeItemType>::BinaryTree(TreeNode *nodePtr) : root(nodePtr)
{
}  // end protected constructor

template<typename TreeItemType>
BinaryTree<TreeItemType>::~BinaryTree()
{
   destroyTree(&root);
}  // end destructor

template<typename TreeItemType>
bool BinaryTree<TreeItemType>::isEmpty() const
{
   return (root == NULL);
}  // end isEmpty

template<typename TreeItemType>
TreeItemType BinaryTree<TreeItemType>::getRootData() const
   throw(TreeException)
{
   if (isEmpty())
      throw TreeException("TreeException: Empty tree");
   return root->item;
}  // end getRootData

template<typename TreeItemType>
void BinaryTree<TreeItemType>::setRootData(const TreeItemType& newItem)
   throw(TreeException)
{
   if (!isEmpty())
      root->item = newItem;
   else
   {
      try
      {
	 root = new TreeNode(newItem, NULL, NULL);
      }
	  catch (std::bad_alloc e)
      {
	 throw TreeException("TreeException: setRootData cannot allocate memory");
      }  // end try
    }  // end if
}  // end setRootData

template<typename TreeItemType>
void BinaryTree<TreeItemType>::attachLeft(const TreeItemType& newItem)
   throw(TreeException)
{
   if (isEmpty())
      throw TreeException("TreeException: Empty tree");
   else if (root->leftChildPtr != NULL)
		throw TreeException("TreeException: Cannot overwrite left subtree");
   else  // Assertion: nonempty tree; no left child
   {
      try
      {
	 root->leftChildPtr = new TreeNode(newItem, NULL, NULL);
      }
	  catch (std::bad_alloc e)
      {
	 throw TreeException("TreeException: attachLeft cannot allocate memory");
      }  // `end try
   }  // end if
}  // end attachLeft

template<typename TreeItemType>
void BinaryTree<TreeItemType>::attachRight(const TreeItemType& newItem)
   throw(TreeException)
{
   if (isEmpty())
      throw TreeException("TreeException: Empty tree");
   else if (root->rightChildPtr != NULL)
      throw TreeException(
	 "TreeException: Cannot overwrite right subtree");
   else  // Assertion: nonempty tree; no right child
   {
      try
      {
	 root->rightChildPtr = new TreeNode(newItem, NULL, NULL);
      }
	  catch (std::bad_alloc e)
      {
	 throw TreeException("TreeException: attachRight cannot allocate memory");
      }  // `end try
   }  // end if
}  // end attachRight

template<typename TreeItemType>
void BinaryTree<TreeItemType>::attachLeftSubtree(BinaryTree& leftTree)
   throw(TreeException)
{
   if (isEmpty())
      throw TreeException("TreeException: Empty tree");
   else if (root->leftChildPtr != NULL)
      throw TreeException(
	 "TreeException: Cannot overwrite left subtree");
   else  // Assertion: nonempty tree; no left child
   {  root->leftChildPtr = leftTree.root;
      leftTree.root = NULL;
   }  // end if
}  // end attachLeftSubtree

template<typename TreeItemType>
void BinaryTree<TreeItemType>::attachRightSubtree(BinaryTree& rightTree)
   throw(TreeException)
{
   if (isEmpty())
      throw TreeException("TreeException: Empty tree");
   else if (root->rightChildPtr != NULL)
      throw TreeException(
	 "TreeException: Cannot overwrite right subtree");
   else  // Assertion: nonempty tree; no right child
   {  root->rightChildPtr = rightTree.root;
      rightTree.root = NULL;
   }  // end if
}  // end attachRightSubtree

template<typename TreeItemType>
void BinaryTree<TreeItemType>::detachLeftSubtree(BinaryTree& leftTree)
   throw(TreeException)
{
   if (isEmpty())
      throw TreeException("TreeException: Empty tree");
   else
   {  leftTree = BinaryTree(root->leftChildPtr);
      root->leftChildPtr = NULL;
   }  // end if
}  // end detachLeftSubtree

template<typename TreeItemType>
void BinaryTree<TreeItemType>::detachRightSubtree(BinaryTree& rightTree)
   throw(TreeException)
{
   if (isEmpty())
      throw TreeException("TreeException: Empty tree");
   else
   {  rightTree = BinaryTree(root->rightChildPtr);
      root->rightChildPtr = NULL;
   }  // end if
}  // end detachRightSubtree

template<typename TreeItemType>
BinaryTree<TreeItemType> BinaryTree<TreeItemType>::getLeftSubtree() const
   throw(TreeException)
{
   TreeNode *subTreePtr;

   if (isEmpty())
      return BinaryTree();
   else
   {  copyTree(root->leftChildPtr, &subTreePtr);
      return BinaryTree(subTreePtr);
   }  // end if
}  // end getLeftSubtree

template<typename TreeItemType>
BinaryTree<TreeItemType> BinaryTree<TreeItemType>::getRightSubtree() const
   throw(TreeException)
{
   TreeNode *subTreePtr;

   if (isEmpty())
      return BinaryTree();
   else
   {  copyTree(root->rightChildPtr, &subTreePtr);
      return BinaryTree(subTreePtr);
   }  // end if
}  // end getRightSubtree

template<typename TreeItemType>
void BinaryTree<TreeItemType>::preorderTraverse(
			void (*visit)(TreeItemType &anItem)) const
{
   preorder(root, visit);
}  // end preorderTraverse

template<typename TreeItemType>
void BinaryTree<TreeItemType>::inorderTraverse(
			void (*visit)(TreeItemType &anItem)) const
{
   inorder(root, visit);
}  // end inorderTraverse

template<typename TreeItemType>
void BinaryTree<TreeItemType>::postorderTraverse(
			void (*visit)(TreeItemType &anItem)) const
{
   postorder(root, visit);
}  // end postorderTraverse

template<typename TreeItemType>
BinaryTree<TreeItemType>& BinaryTree<TreeItemType>::operator=(const BinaryTree& rhs)
   throw(TreeException)
{
   if (this != &rhs)
   {  destroyTree(&root);  // deallocate left-hand side
      copyTree(rhs.root, &root);  // copy right-hand side
   }  // end if
   return *this;
}  // end operator=

template<typename TreeItemType>
void BinaryTree<TreeItemType>::copyTree(TreeNode *treePtr,
                          TreeNode ** newTreePtr) const
   throw(TreeException)
{
   // preorder traversal
   if (treePtr != NULL)
   {  // copy node
      try
      {
	 (*newTreePtr) = new TreeNode(treePtr->item, NULL, NULL);
	 copyTree(treePtr->leftChildPtr, &(*newTreePtr)->leftChildPtr);
	 copyTree(treePtr->rightChildPtr, &(*newTreePtr)->rightChildPtr);
      }
	  catch (std::bad_alloc e)
      {
	 throw TreeException("TreeException: copyTree cannot allocate memory");
      }  // `end try
   }
   else
      newTreePtr = NULL;  // copy empty tree
}  // end copyTree

template<typename TreeItemType>
void BinaryTree<TreeItemType>::destroyTree(TreeNode ** treePtr)
{
   // postorder traversal
   if (*treePtr != NULL)
   {  destroyTree(&(*treePtr)->leftChildPtr);
      destroyTree(&(*treePtr)->rightChildPtr);
      delete *treePtr;
      *treePtr = NULL;
   }  // end if
}  // end destroyTree



template<typename TreeItemType>
void BinaryTree<TreeItemType>::setRootPtr(TreeNode *newRoot)
{
   root = newRoot;
}  // end setRoot

template<typename TreeItemType>
void BinaryTree<TreeItemType>::getChildPtrs(TreeNode *nodePtr,
                              TreeNode ** leftPtr,
                              TreeNode ** rightPtr) const
{
   *leftPtr = nodePtr->leftChildPtr;
   *rightPtr = nodePtr->rightChildPtr;
}  // end getChildPtrs

template<typename TreeItemType>
void BinaryTree<TreeItemType>::setChildPtrs(TreeNode *nodePtr,
                              TreeNode *leftPtr,
                              TreeNode *rightPtr)
{
   nodePtr->leftChildPtr = leftPtr;
   nodePtr->rightChildPtr = rightPtr;
}  // end setChildPtrs

template<typename TreeItemType>
void BinaryTree<TreeItemType>::preorder(TreeNode *treePtr,
                          void (*visit)(TreeItemType &anItem)) const
{
   if (treePtr != NULL)
   {  (*visit)(treePtr->item);
      preorder(treePtr->leftChildPtr, visit);
      preorder(treePtr->rightChildPtr, visit);
   }  // end if
}  // end preorder

template<typename TreeItemType>
void BinaryTree<TreeItemType>::inorder(TreeNode *treePtr,
                         void (*visit)(TreeItemType &anItem)) const
{
   if (treePtr != NULL)
   {  inorder(treePtr->leftChildPtr, visit);
      (*visit)(treePtr->item);
      inorder(treePtr->rightChildPtr, visit);
   }  // end if
}  // end inorder

template<typename TreeItemType>
void BinaryTree<TreeItemType>::postorder(TreeNode *treePtr,
                           void (*visit)(TreeItemType &anItem)) const
{
   if (treePtr != NULL)
   {  postorder(treePtr->leftChildPtr, visit);
      postorder(treePtr->rightChildPtr, visit);
      (*visit)(treePtr->item);
   } // end if
}  // end postorder
// End of implementation file.

#endif

